1. Technical Field
The technical field of the present specification relates in general to a method and system for data processing and in particular to a method and system for determining an address within memory. Still more particularly, the technical field relates to a processor and method for translating a nonphysical address into a physical address utilizing a selectively nonsequential search of page table entries.
2. Description of the Related Art
The memory system of a typical personal computer includes one or more nonvolatile mass storage devices, such as magnetic or optical disks, and a volatile random access memory (RAM), which can include both high speed cache memory and slower main memory. In order to provide enough addresses for memory-mapped I/O as well as the data and instructions utilized by operating system and application software, the processor of a personal computer typically utilizes a virtual address space that includes a much larger number of addresses than physically exist in RAM. Therefore, to perform memory-mapped I/O or to access RAM, the processor maps the virtual addresses into physical addresses assigned to particular I/O devices or physical locations within RAM.
In the PowerPC.TM. RISC architecture, which is described in PowerPC.TM. 603 RISC Microprocessor User's Manual, available from IBM Corporation as Order No. MPR603UMU-01, the virtual address space is partitioned into a number of uniformly-sized memory pages, which each have an address descriptor called a Page Table Entry (PTE). The PTE corresponding to a particular memory page contains the virtual address of the memory page as well as the associated physical address of the page frame, thereby enabling the processor to translate any virtual address within the memory page into a physical address in memory. The PTEs, which are created in memory by the operating system, reside in Page Table Entry Groups (PTEGs), which can each contain, for example, up to eight PTEs. According to the PowerPC.TM. architecture, a particular PTE can reside in any location in either of a primary PTEG or a secondary PTEG, which are selected by performing primary and secondary hashing functions, respectively, on the virtual address of the memory page. In order to improve performance, the processor also includes a Translation Lookaside Buffer (TLB) that stores the most recently accessed PTEs for quick access.
Although a virtual address can usually be translated by reference to the TLB because of the locality of reference, if a TLB miss occurs, that is, if the PTE required to translate the virtual address of a particular memory page into a physical address is not resident within the TLB, the processor must search the PTEs in memory in order to reload the required PTE into the TLB and translate the virtual address of the memory page. Conventionally, the search, which can be performed either in hardware or by a software interrupt handler, sequentially examines the contents of the primary PTEG, and if no match is found in the primary PTEG, the contents of the secondary PTEG. If a match is found in either the primary or the secondary PTEG, history bits for the memory page are updated, if required, and the PTE is loaded into the TLB in order to perform the address translation. However, if no match is found in either the primary or secondary PTEG, a page fault exception is reported to the processor and an exception handler is executed to load the requested memory page from nonvolatile mass storage into memory.
Although PTE searches are infrequently required, PTE searches utilizing the above-described sequential search of the primary and secondary PTEGs do slow processor performance, particularly when the PTE searches are performed in software. This performance penalty is due, for example, to the delay incurred when the primary PTEG resides in main memory, but the secondary PTEG resides in high speed cache memory. Utilizing the conventional sequential search of the primary and secondary PTEGs, the search of the secondary PTEG is delayed until the primary PTEG is loaded into cache memory and searched. As should thus be apparent, an improved method for translating a virtual (nonphysical) address into a physical address is needed that efficiently searches PTEGs in memory in response to a TLB miss.